home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / snip1292.zip / COMBIN.C < prev    next >
C/C++ Source or Header  |  1992-12-26  |  2KB  |  67 lines
  1. /*
  2. ** Compute C(n,m) = the number of combinations of n items,
  3. ** taken m at a time.
  4. **
  5. ** Written by Thad Smith III, Boulder County, CO.
  6. ** Released to the Public Domain  10/14/91.
  7. **
  8. ** The def of this function is
  9. **      C(n,m)  = n! / (m! * (n-m)!).
  10. ** Computing this formula can cause overflow for large values of n,
  11. ** even when C(n,m) would be defined.
  12. **
  13. ** The first version will not overflow if C(n,m) * (n-m+1) < ULONG_MAX.
  14. ** The second version will not overflow if C(n,m) < ULONG_MAX, but
  15. ** is slightly more complex.
  16. ** Function domain: n >= 0,  0 <= m <= n.
  17. **
  18. ** Both versions work by reducing the product as it is computed.  It
  19. ** relies on the property that the product on n consecutive integers
  20. ** must be evenly divisible by n.
  21. **
  22. ** The first version can be changed to make cnm and the return value
  23. ** double to extend the range of the function.
  24. */
  25.  
  26. unsigned long ncomb1 (int n, int m)
  27. {
  28.       unsigned long cnm = 1UL;
  29.       int i;
  30.  
  31.       if (m*2 >n) m = n-m;
  32.       for (i=1 ; i <= m; n--, i++)
  33.             cnm = cnm * n / i;
  34.       return cnm;
  35. }
  36.  
  37. unsigned long ncomb2 (int n, int m)
  38. {
  39.       unsigned long cnm = 1UL;
  40.       int i, f;
  41.  
  42.       if (m*2 >n) m = n-m;
  43.       for (i=1 ; i <= m; n--, i++)
  44.       {
  45.             if ((f=n) % i == 0)
  46.                   f   /= i;
  47.             else  cnm /= i;
  48.             cnm *= f;
  49.       }
  50.       return cnm;
  51. }
  52.  
  53. #ifdef TEST
  54.  
  55. #include <stdio.h>
  56. #include <stdlib.h>
  57.  
  58. main (int argc, char *argv[]) {
  59.     int n,m;
  60.     n = atoi (argv[1]);
  61.     m = atoi (argv[2]);
  62.     printf ("ncomb1 = %lu, ncomb2 = %lu\n", ncomb1(n,m), ncomb2(n,m));
  63.     return 0;
  64. }
  65.  
  66. #endif
  67.